#if 0
//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2012 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#include <buola/image/rasterizer/cspanrasterizer.h>

namespace buola { namespace img {

struct CSpanRasterizer::SEdge
{
    int mHeightLeft;

    int mDir; ///< original sign: +1 for downwards, -1 for upwards
    int mVertical;

    int mXQuo,mXRem;
    int mDXDYQuo,mDXDYRem;
    int mDXDYFullQuo,mDXDYFullRem;

    int mYTop;
    int mDY;
};

struct CSpanRasterizer::SPolygon
{
    inline int BucketIndex(int y)   {   return (y-mYMin)/GRID_Y;    }
    
private:
    int mYMin,mYMax;
    std::vector<std::vector<SEdge>> mBuckets;
};

/*namespace img*/ } /*namespace buola*/ }

/* A cell records the effect on pixel coverage of polygon edges
 * passing through a pixel.  It contains two accumulators of pixel
 * coverage.
 *
 * Consider the effects of a polygon edge on the coverage of a pixel
 * it intersects and that of the following one.  The coverage of the
 * following pixel is the height of the edge multiplied by the width
 * of the pixel, and the coverage of the pixel itself is the area of
 * the trapezoid formed by the edge and the right side of the pixel.
 *
 * +-----------------------+-----------------------+
 * |                       |                       |
 * |                       |                       |
 * |_______________________|_______________________|
 * |   \...................|.......................|\
 * |    \..................|.......................| |
 * |     \.................|.......................| |
 * |      \....covered.....|.......................| |
 * |       \....area.......|.......................| } covered height
 * |        \..............|.......................| |
 * |uncovered\.............|.......................| |
 * |  area    \............|.......................| |
 * |___________\...........|.......................|/
 * |                       |                       |
 * |                       |                       |
 * |                       |                       |
 * +-----------------------+-----------------------+
 *
 * Since the coverage of the following pixel will always be a multiple
 * of the width of the pixel, we can store the height of the covered
 * area instead.  The coverage of the pixel itself is the total
 * coverage minus the area of the uncovered area to the left of the
 * edge.  As it's faster to compute the uncovered area we only store
 * that and subtract it from the total coverage later when forming
 * spans to blit.
 *
 * The heights and areas are signed, with left edges of the polygon
 * having positive sign and right edges having negative sign.  When
 * two edges intersect they swap their left/rightness so their
 * contribution above and below the intersection point must be
 * computed separately. */
struct cell {
    struct cell     *next;
    int          x;
    int16_t      uncovered_area;
    int16_t      covered_height;
};

/* A cell list represents the scan line sparsely as cells ordered by
 * ascending x.  It is geared towards scanning the cells in order
 * using an internal cursor. */
struct cell_list {
    /* Sentinel nodes */
    struct cell head, tail;

    /* Cursor state for iterating through the cell list. */
    struct cell *cursor, *rewind;

    /* Cells in the cell list are owned by the cell list and are
     * allocated from this pool.  */
    struct {
    struct pool base[1];
    struct cell embedded[32];
    } cell_pool;
};

struct cell_pair {
    struct cell *cell1;
    struct cell *cell2;
};

/* The active list contains edges in the current scan line ordered by
 * the x-coordinate of the intercept of the edge and the scan line. */
struct active_list {
    /* Leftmost edge on the current scan line. */
    struct edge head, tail;

    /* A lower bound on the height of the active edges is used to
     * estimate how soon some active edge ends.  We can't advance the
     * scan conversion by a full pixel row if an edge ends somewhere
     * within it. */
    grid_scaled_y_t min_height;
    int is_vertical;
};

struct glitter_scan_converter {
    struct polygon  polygon[1];
    struct active_list  active[1];
    struct cell_list    coverages[1];

    cairo_half_open_span_t *spans;
    cairo_half_open_span_t spans_embedded[64];

    /* Clip box. */
    grid_scaled_x_t xmin, xmax;
    grid_scaled_y_t ymin, ymax;
};

/* Compute the floored division a/b. Assumes / and % perform symmetric
 * division. */
inline static struct quorem
floored_divrem(int a, int b)
{
    struct quorem qr;
    qr.quo = a/b;
    qr.rem = a%b;
    if ((a^b)<0 && qr.rem) {
    qr.quo -= 1;
    qr.rem += b;
    }
    return qr;
}

/* Compute the floored division (x*a)/b. Assumes / and % perform symmetric
 * division. */
static struct quorem
floored_muldivrem(int x, int a, int b)
{
    struct quorem qr;
    long long xa = (long long)x*a;
    qr.quo = xa/b;
    qr.rem = xa%b;
    if ((xa>=0) != (b>=0) && qr.rem) {
    qr.quo -= 1;
    qr.rem += b;
    }
    return qr;
}

static struct _pool_chunk *
_pool_chunk_init(
    struct _pool_chunk *p,
    struct _pool_chunk *prev_chunk,
    size_t capacity)
{
    p->prev_chunk = prev_chunk;
    p->size = 0;
    p->capacity = capacity;
    return p;
}

static struct _pool_chunk *
_pool_chunk_create(struct pool *pool, size_t size)
{
    struct _pool_chunk *p;

    p = malloc(size + sizeof(struct _pool_chunk));
    if (unlikely (NULL == p))
    longjmp (*pool->jmp, _cairo_error (CAIRO_STATUS_NO_MEMORY));

    return _pool_chunk_init(p, pool->current, size);
}

static void
pool_init(struct pool *pool,
      jmp_buf *jmp,
      size_t default_capacity,
      size_t embedded_capacity)
{
    pool->jmp = jmp;
    pool->current = pool->sentinel;
    pool->first_free = NULL;
    pool->default_capacity = default_capacity;
    _pool_chunk_init(pool->sentinel, NULL, embedded_capacity);
}

static void
pool_fini(struct pool *pool)
{
    struct _pool_chunk *p = pool->current;
    do {
    while (NULL != p) {
        struct _pool_chunk *prev = p->prev_chunk;
        if (p != pool->sentinel)
        free(p);
        p = prev;
    }
    p = pool->first_free;
    pool->first_free = NULL;
    } while (NULL != p);
}

/* Satisfy an allocation by first allocating a new large enough chunk
 * and adding it to the head of the pool's chunk list. This function
 * is called as a fallback if pool_alloc() couldn't do a quick
 * allocation from the current chunk in the pool. */
static void *
_pool_alloc_from_new_chunk(
    struct pool *pool,
    size_t size)
{
    struct _pool_chunk *chunk;
    void *obj;
    size_t capacity;

    /* If the allocation is smaller than the default chunk size then
     * try getting a chunk off the free list.  Force alloc of a new
     * chunk for large requests. */
    capacity = size;
    chunk = NULL;
    if (size < pool->default_capacity) {
    capacity = pool->default_capacity;
    chunk = pool->first_free;
    if (chunk) {
        pool->first_free = chunk->prev_chunk;
        _pool_chunk_init(chunk, pool->current, chunk->capacity);
    }
    }

    if (NULL == chunk)
    chunk = _pool_chunk_create (pool, capacity);
    pool->current = chunk;

    obj = ((unsigned char*)chunk + sizeof(*chunk) + chunk->size);
    chunk->size += size;
    return obj;
}

/* Allocate size bytes from the pool.  The first allocated address
 * returned from a pool is aligned to sizeof(void*).  Subsequent
 * addresses will maintain alignment as long as multiples of void* are
 * allocated.  Returns the address of a new memory area or %NULL on
 * allocation failures.  The pool retains ownership of the returned
 * memory. */
inline static void *
pool_alloc (struct pool *pool, size_t size)
{
    struct _pool_chunk *chunk = pool->current;

    if (size <= chunk->capacity - chunk->size) {
    void *obj = ((unsigned char*)chunk + sizeof(*chunk) + chunk->size);
    chunk->size += size;
    return obj;
    } else {
    return _pool_alloc_from_new_chunk(pool, size);
    }
}

/* Relinquish all pool_alloced memory back to the pool. */
static void
pool_reset (struct pool *pool)
{
    /* Transfer all used chunks to the chunk free list. */
    struct _pool_chunk *chunk = pool->current;
    if (chunk != pool->sentinel) {
    while (chunk->prev_chunk != pool->sentinel) {
        chunk = chunk->prev_chunk;
    }
    chunk->prev_chunk = pool->first_free;
    pool->first_free = pool->current;
    }
    /* Reset the sentinel as the current chunk. */
    pool->current = pool->sentinel;
    pool->sentinel->size = 0;
}

/* Rewinds the cell list's cursor to the beginning.  After rewinding
 * we're good to cell_list_find() the cell any x coordinate. */
inline static void
cell_list_rewind (struct cell_list *cells)
{
    cells->cursor = &cells->head;
}

inline static void
cell_list_maybe_rewind (struct cell_list *cells, int x)
{
    if (x < cells->cursor->x) {
    cells->cursor = cells->rewind;
    if (x < cells->cursor->x)
        cells->cursor = &cells->head;
    }
}

inline static void
cell_list_set_rewind (struct cell_list *cells)
{
    cells->rewind = cells->cursor;
}

static void
cell_list_init(struct cell_list *cells, jmp_buf *jmp)
{
    pool_init(cells->cell_pool.base, jmp,
          256*sizeof(struct cell),
          sizeof(cells->cell_pool.embedded));
    cells->tail.next = NULL;
    cells->tail.x = INT_MAX;
    cells->head.x = INT_MIN;
    cells->head.next = &cells->tail;
    cell_list_rewind (cells);
}

static void
cell_list_fini(struct cell_list *cells)
{
    pool_fini (cells->cell_pool.base);
}

/* Empty the cell list.  This is called at the start of every pixel
 * row. */
inline static void
cell_list_reset (struct cell_list *cells)
{
    cell_list_rewind (cells);
    cells->head.next = &cells->tail;
    pool_reset (cells->cell_pool.base);
}

inline static struct cell *
cell_list_alloc (struct cell_list *cells,
         struct cell *tail,
         int x)
{
    struct cell *cell;

    cell = pool_alloc (cells->cell_pool.base, sizeof (struct cell));
    cell->next = tail->next;
    tail->next = cell;
    cell->x = x;
    *(uint32_t *)&cell->uncovered_area = 0;

    return cell;
}

/* Find a cell at the given x-coordinate.  Returns %NULL if a new cell
 * needed to be allocated but couldn't be.  Cells must be found with
 * non-decreasing x-coordinate until the cell list is rewound using
 * cell_list_rewind(). Ownership of the returned cell is retained by
 * the cell list. */
inline static struct cell *
cell_list_find (struct cell_list *cells, int x)
{
    struct cell *tail = cells->cursor;

    if (tail->x == x)
    return tail;

    while (1) {
    UNROLL3({
        if (tail->next->x > x)
            break;
        tail = tail->next;
    });
    }

    if (tail->x != x)
    tail = cell_list_alloc (cells, tail, x);
    return cells->cursor = tail;

}

/* Find two cells at x1 and x2.  This is exactly equivalent
 * to
 *
 *   pair.cell1 = cell_list_find(cells, x1);
 *   pair.cell2 = cell_list_find(cells, x2);
 *
 * except with less function call overhead. */
inline static struct cell_pair
cell_list_find_pair(struct cell_list *cells, int x1, int x2)
{
    struct cell_pair pair;

    pair.cell1 = cells->cursor;
    while (1) {
    UNROLL3({
        if (pair.cell1->next->x > x1)
            break;
        pair.cell1 = pair.cell1->next;
    });
    }
    if (pair.cell1->x != x1)
    pair.cell1 = cell_list_alloc (cells, pair.cell1, x1);

    pair.cell2 = pair.cell1;
    while (1) {
    UNROLL3({
        if (pair.cell2->next->x > x2)
            break;
        pair.cell2 = pair.cell2->next;
    });
    }
    if (pair.cell2->x != x2)
    pair.cell2 = cell_list_alloc (cells, pair.cell2, x2);

    cells->cursor = pair.cell2;
    return pair;
}

/* Add a subpixel span covering [x1, x2) to the coverage cells. */
inline static void
cell_list_add_subspan(struct cell_list *cells,
              grid_scaled_x_t x1,
              grid_scaled_x_t x2)
{
    int ix1, fx1;
    int ix2, fx2;

    if (x1 == x2)
    return;

    GRID_X_TO_INT_FRAC(x1, ix1, fx1);
    GRID_X_TO_INT_FRAC(x2, ix2, fx2);

    if (ix1 != ix2) {
    struct cell_pair p;
    p = cell_list_find_pair(cells, ix1, ix2);
    p.cell1->uncovered_area += 2*fx1;
    ++p.cell1->covered_height;
    p.cell2->uncovered_area -= 2*fx2;
    --p.cell2->covered_height;
    } else {
    struct cell *cell = cell_list_find(cells, ix1);
    cell->uncovered_area += 2*(fx1-fx2);
    }
}

/* Adds the analytical coverage of an edge crossing the current pixel
 * row to the coverage cells and advances the edge's x position to the
 * following row.
 *
 * This function is only called when we know that during this pixel row:
 *
 * 1) The relative order of all edges on the active list doesn't
 * change.  In particular, no edges intersect within this row to pixel
 * precision.
 *
 * 2) No new edges start in this row.
 *
 * 3) No existing edges end mid-row.
 *
 * This function depends on being called with all edges from the
 * active list in the order they appear on the list (i.e. with
 * non-decreasing x-coordinate.)  */
static void
cell_list_render_edge(struct cell_list *cells,
              struct edge *edge,
              int sign)
{
    grid_scaled_y_t y1, y2, dy;
    grid_scaled_x_t dx;
    int ix1, ix2;
    grid_scaled_x_t fx1, fx2;

    struct quorem x1 = edge->x;
    struct quorem x2 = x1;

    if (! edge->vertical) {
    x2.quo += edge->dxdy_full.quo;
    x2.rem += edge->dxdy_full.rem;
    if (x2.rem >= 0) {
        ++x2.quo;
        x2.rem -= edge->dy;
    }

    edge->x = x2;
    }

    GRID_X_TO_INT_FRAC(x1.quo, ix1, fx1);
    GRID_X_TO_INT_FRAC(x2.quo, ix2, fx2);

    /* Edge is entirely within a column? */
    if (ix1 == ix2) {
    /* We always know that ix1 is >= the cell list cursor in this
     * case due to the no-intersections precondition.  */
    struct cell *cell = cell_list_find(cells, ix1);
    cell->covered_height += sign*GRID_Y;
    cell->uncovered_area += sign*(fx1 + fx2)*GRID_Y;
    return;
    }

    /* Orient the edge left-to-right. */
    dx = x2.quo - x1.quo;
    if (dx >= 0) {
    y1 = 0;
    y2 = GRID_Y;
    } else {
    int tmp;
    tmp = ix1; ix1 = ix2; ix2 = tmp;
    tmp = fx1; fx1 = fx2; fx2 = tmp;
    dx = -dx;
    sign = -sign;
    y1 = GRID_Y;
    y2 = 0;
    }
    dy = y2 - y1;

    /* Add coverage for all pixels [ix1,ix2] on this row crossed
     * by the edge. */
    {
    struct cell_pair pair;
    struct quorem y = floored_divrem((GRID_X - fx1)*dy, dx);

    /* When rendering a previous edge on the active list we may
     * advance the cell list cursor past the leftmost pixel of the
     * current edge even though the two edges don't intersect.
     * e.g. consider two edges going down and rightwards:
     *
     *  --\_+---\_+-----+-----+----
     *      \_    \_    |     |
     *      | \_  | \_  |     |
     *      |   \_|   \_|     |
     *      |     \_    \_    |
     *  ----+-----+-\---+-\---+----
     *
     * The left edge touches cells past the starting cell of the
     * right edge.  Fortunately such cases are rare.
     *
     * The rewinding is never necessary if the current edge stays
     * within a single column because we've checked before calling
     * this function that the active list order won't change. */
    cell_list_maybe_rewind(cells, ix1);

    pair = cell_list_find_pair(cells, ix1, ix1+1);
    pair.cell1->uncovered_area += sign*y.quo*(GRID_X + fx1);
    pair.cell1->covered_height += sign*y.quo;
    y.quo += y1;

    if (ix1+1 < ix2) {
        struct quorem dydx_full = floored_divrem(GRID_X*dy, dx);
        struct cell *cell = pair.cell2;

        ++ix1;
        do {
        grid_scaled_y_t y_skip = dydx_full.quo;
        y.rem += dydx_full.rem;
        if (y.rem >= dx) {
            ++y_skip;
            y.rem -= dx;
        }

        y.quo += y_skip;

        y_skip *= sign;
        cell->uncovered_area += y_skip*GRID_X;
        cell->covered_height += y_skip;

        ++ix1;
        cell = cell_list_find(cells, ix1);
        } while (ix1 != ix2);

        pair.cell2 = cell;
    }
    pair.cell2->uncovered_area += sign*(y2 - y.quo)*fx2;
    pair.cell2->covered_height += sign*(y2 - y.quo);
    }
}

static void
polygon_init (struct polygon *polygon, jmp_buf *jmp)
{
    polygon->ymin = polygon->ymax = 0;
    polygon->y_buckets = polygon->y_buckets_embedded;
    pool_init (polygon->edge_pool.base, jmp,
           8192 - sizeof (struct _pool_chunk),
           sizeof (polygon->edge_pool.embedded));
}

static void
polygon_fini (struct polygon *polygon)
{
    if (polygon->y_buckets != polygon->y_buckets_embedded)
    free (polygon->y_buckets);

    pool_fini (polygon->edge_pool.base);
}

/* Empties the polygon of all edges. The polygon is then prepared to
 * receive new edges and clip them to the vertical range
 * [ymin,ymax). */
static glitter_status_t
polygon_reset (struct polygon *polygon,
           grid_scaled_y_t ymin,
           grid_scaled_y_t ymax)
{
    unsigned h = ymax - ymin;
    unsigned num_buckets = EDGE_Y_BUCKET_INDEX(ymax + GRID_Y-1, ymin);

    pool_reset(polygon->edge_pool.base);

    if (unlikely (h > 0x7FFFFFFFU - GRID_Y))
    goto bail_no_mem; /* even if you could, you wouldn't want to. */

    if (polygon->y_buckets != polygon->y_buckets_embedded)
    free (polygon->y_buckets);

    polygon->y_buckets =  polygon->y_buckets_embedded;
    if (num_buckets > ARRAY_LENGTH (polygon->y_buckets_embedded)) {
    polygon->y_buckets = _cairo_malloc_ab (num_buckets,
                           sizeof (struct edge *));
    if (unlikely (NULL == polygon->y_buckets))
        goto bail_no_mem;
    }
    memset (polygon->y_buckets, 0, num_buckets * sizeof (struct edge *));

    polygon->ymin = ymin;
    polygon->ymax = ymax;
    return GLITTER_STATUS_SUCCESS;

bail_no_mem:
    polygon->ymin = 0;
    polygon->ymax = 0;
    return GLITTER_STATUS_NO_MEMORY;
}

static void
_polygon_insert_edge_into_its_y_bucket(struct polygon *polygon,
                       struct edge *e)
{
    unsigned ix = EDGE_Y_BUCKET_INDEX(e->ytop, polygon->ymin);
    struct edge **ptail = &polygon->y_buckets[ix];
    e->next = *ptail;
    *ptail = e;
}

inline static void
polygon_add_edge (struct polygon *polygon,
          const cairo_edge_t *edge)
{
    struct edge *e;
    grid_scaled_x_t dx;
    grid_scaled_y_t dy;
    grid_scaled_y_t ytop, ybot;
    grid_scaled_y_t ymin = polygon->ymin;
    grid_scaled_y_t ymax = polygon->ymax;

    if (unlikely (edge->top >= ymax || edge->bottom <= ymin))
    return;

    e = pool_alloc (polygon->edge_pool.base, sizeof (struct edge));

    dx = edge->line.p2.x - edge->line.p1.x;
    dy = edge->line.p2.y - edge->line.p1.y;
    e->dy = dy;
    e->dir = edge->dir;

    ytop = edge->top >= ymin ? edge->top : ymin;
    ybot = edge->bottom <= ymax ? edge->bottom : ymax;
    e->ytop = ytop;
    e->height_left = ybot - ytop;

    if (dx == 0) {
    e->vertical = TRUE;
    e->x.quo = edge->line.p1.x;
    e->x.rem = 0;
    e->dxdy.quo = 0;
    e->dxdy.rem = 0;
    e->dxdy_full.quo = 0;
    e->dxdy_full.rem = 0;
    } else {
    e->vertical = FALSE;
    e->dxdy = floored_divrem (dx, dy);
    if (ytop == edge->line.p1.y) {
        e->x.quo = edge->line.p1.x;
        e->x.rem = 0;
    } else {
        e->x = floored_muldivrem (ytop - edge->line.p1.y, dx, dy);
        e->x.quo += edge->line.p1.x;
    }

    if (e->height_left >= GRID_Y) {
        e->dxdy_full = floored_muldivrem (GRID_Y, dx, dy);
    } else {
        e->dxdy_full.quo = 0;
        e->dxdy_full.rem = 0;
    }
    }

    _polygon_insert_edge_into_its_y_bucket (polygon, e);

    e->x.rem -= dy;     /* Bias the remainder for faster
                 * edge advancement. */
}

static void
active_list_reset (struct active_list *active)
{
    active->head.vertical = 1;
    active->head.height_left = INT_MAX;
    active->head.x.quo = INT_MIN;
    active->head.prev = NULL;
    active->head.next = &active->tail;
    active->tail.prev = &active->head;
    active->tail.next = NULL;
    active->tail.x.quo = INT_MAX;
    active->tail.height_left = INT_MAX;
    active->tail.vertical = 1;
    active->min_height = 0;
    active->is_vertical = 1;
}

static void
active_list_init(struct active_list *active)
{
    active_list_reset(active);
}

/*
 * Merge two sorted edge lists.
 * Input:
 *  - head_a: The head of the first list.
 *  - head_b: The head of the second list; head_b cannot be NULL.
 * Output:
 * Returns the head of the merged list.
 *
 * Implementation notes:
 * To make it fast (in particular, to reduce to an insertion sort whenever
 * one of the two input lists only has a single element) we iterate through
 * a list until its head becomes greater than the head of the other list,
 * then we switch their roles. As soon as one of the two lists is empty, we
 * just attach the other one to the current list and exit.
 * Writes to memory are only needed to "switch" lists (as it also requires
 * attaching to the output list the list which we will be iterating next) and
 * to attach the last non-empty list.
 */
static struct edge *
merge_sorted_edges (struct edge *head_a, struct edge *head_b)
{
    struct edge *head, **next, *prev;
    int32_t x;

    prev = head_a->prev;
    next = &head;
    if (head_a->x.quo <= head_b->x.quo) {
    head = head_a;
    } else {
    head = head_b;
    head_b->prev = prev;
    goto start_with_b;
    }

    do {
    x = head_b->x.quo;
    while (head_a != NULL && head_a->x.quo <= x) {
        prev = head_a;
        next = &head_a->next;
        head_a = head_a->next;
    }

    head_b->prev = prev;
    *next = head_b;
    if (head_a == NULL)
        return head;

start_with_b:
    x = head_a->x.quo;
    while (head_b != NULL && head_b->x.quo <= x) {
        prev = head_b;
        next = &head_b->next;
        head_b = head_b->next;
    }

    head_a->prev = prev;
    *next = head_a;
    if (head_b == NULL)
        return head;
    } while (1);
}

/*
 * Sort (part of) a list.
 * Input:
 *  - list: The list to be sorted; list cannot be NULL.
 *  - limit: Recursion limit.
 * Output:
 *  - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
 *              input list; if the input list has fewer elements, head_out be a sorted list
 *              containing all the elements of the input list.
 * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
 * all the elements of the input list).
 *
 * Implementation notes:
 * Special case single element list, unroll/inline the sorting of the first two elements.
 * Some tail recursion is used since we iterate on the bottom-up solution of the problem
 * (we start with a small sorted list and keep merging other lists of the same size to it).
 */
static struct edge *
sort_edges (struct edge *list,
        unsigned int level,
        struct edge **head_out)
{
    struct edge *head_other, *remaining;
    unsigned int i;

    head_other = list->next;

    if (head_other == NULL) {
    *head_out = list;
    return NULL;
    }

    remaining = head_other->next;
    if (list->x.quo <= head_other->x.quo) {
    *head_out = list;
    head_other->next = NULL;
    } else {
    *head_out = head_other;
    head_other->prev = list->prev;
    head_other->next = list;
    list->prev = head_other;
    list->next = NULL;
    }

    for (i = 0; i < level && remaining; i++) {
    remaining = sort_edges (remaining, i, &head_other);
    *head_out = merge_sorted_edges (*head_out, head_other);
    }

    return remaining;
}

 static struct edge *
merge_unsorted_edges (struct edge *head, struct edge *unsorted)
{
    sort_edges (unsorted, UINT_MAX, &unsorted);
    return merge_sorted_edges (head, unsorted);
}

/* Test if the edges on the active list can be safely advanced by a
 * full row without intersections or any edges ending. */
inline static int
can_do_full_row (struct active_list *active)
{
    const struct edge *e;
    int prev_x = INT_MIN;

    /* Recomputes the minimum height of all edges on the active
     * list if we have been dropping edges. */
    if (active->min_height <= 0) {
    int min_height = INT_MAX;
    int is_vertical = 1;

    e = active->head.next;
    while (NULL != e) {
        if (e->height_left < min_height)
        min_height = e->height_left;
        is_vertical &= e->vertical;
        e = e->next;
    }

    active->is_vertical = is_vertical;
    active->min_height = min_height;
    }

    if (active->min_height < GRID_Y)
    return 0;

    /* Check for intersections as no edges end during the next row. */
    for (e = active->head.next; e != &active->tail; e = e->next) {
    struct quorem x = e->x;

    if (! e->vertical) {
        x.quo += e->dxdy_full.quo;
        x.rem += e->dxdy_full.rem;
        if (x.rem >= 0)
        ++x.quo;
    }

    if (x.quo < prev_x)
        return 0;

    prev_x = x.quo;
    }

    return 1;
}

/* Merges edges on the given subpixel row from the polygon to the
 * active_list. */
inline static void
active_list_merge_edges_from_bucket(struct active_list *active,
                    struct edge *edges)
{
    active->head.next = merge_unsorted_edges (active->head.next, edges);
}

inline static void
polygon_fill_buckets (struct active_list *active,
              struct edge *edge,
              int y,
              struct edge **buckets)
{
    grid_scaled_y_t min_height = active->min_height;
    int is_vertical = active->is_vertical;

    while (edge) {
    struct edge *next = edge->next;
    int suby = edge->ytop - y;
    if (buckets[suby])
        buckets[suby]->prev = edge;
    edge->next = buckets[suby];
    edge->prev = NULL;
    buckets[suby] = edge;
    if (edge->height_left < min_height)
        min_height = edge->height_left;
    is_vertical &= edge->vertical;
    edge = next;
    }

    active->is_vertical = is_vertical;
    active->min_height = min_height;
}

inline static void
sub_row (struct active_list *active,
     struct cell_list *coverages,
     unsigned int mask)
{
    struct edge *edge = active->head.next;
    int xstart = INT_MIN, prev_x = INT_MIN;
    int winding = 0;

    cell_list_rewind (coverages);

    while (&active->tail != edge) {
    struct edge *next = edge->next;
    int xend = edge->x.quo;

    if (--edge->height_left) {
        edge->x.quo += edge->dxdy.quo;
        edge->x.rem += edge->dxdy.rem;
        if (edge->x.rem >= 0) {
        ++edge->x.quo;
        edge->x.rem -= edge->dy;
        }

        if (edge->x.quo < prev_x) {
        struct edge *pos = edge->prev;
        pos->next = next;
        next->prev = pos;
        do {
            pos = pos->prev;
        } while (edge->x.quo < pos->x.quo);
        pos->next->prev = edge;
        edge->next = pos->next;
        edge->prev = pos;
        pos->next = edge;
        } else
        prev_x = edge->x.quo;
        active->min_height = -1;
    } else {
        edge->prev->next = next;
        next->prev = edge->prev;
    }

    winding += edge->dir;
    if ((winding & mask) == 0) {
        if (next->x.quo != xend) {
        cell_list_add_subspan (coverages, xstart, xend);
        xstart = INT_MIN;
        }
    } else if (xstart == INT_MIN)
        xstart = xend;

    edge = next;
    }
}

inline static void dec (struct active_list *a, struct edge *e, int h)
{
    e->height_left -= h;
    if (e->height_left == 0) {
    e->prev->next = e->next;
    e->next->prev = e->prev;
    a->min_height = -1;
    }
}

inline static void full_step (struct edge *e)
{
    if (! e->vertical) {
    e->x.quo += e->dxdy_full.quo;
    e->x.rem += e->dxdy_full.rem;
    if (e->x.rem >= 0) {
        ++e->x.quo;
        e->x.rem -= e->dy;
    }
    }
}

static void
full_row (struct active_list *active,
      struct cell_list *coverages,
      unsigned int mask)
{
    struct edge *left = active->head.next;

    while (&active->tail != left) {
    struct edge *right;
    int winding;

    dec (active, left, GRID_Y);

    winding = left->dir;
    right = left->next;
    do {
        dec (active, right, GRID_Y);

        winding += right->dir;
        if ((winding & mask) == 0 && right->next->x.quo != right->x.quo)
        break;

        full_step (right);

        right = right->next;
    } while (1);

    cell_list_set_rewind (coverages);
    cell_list_render_edge (coverages, left, +1);
    cell_list_render_edge (coverages, right, -1);

    left = right->next;
    }
}

static void
_glitter_scan_converter_init(glitter_scan_converter_t *converter, jmp_buf *jmp)
{
    polygon_init(converter->polygon, jmp);
    active_list_init(converter->active);
    cell_list_init(converter->coverages, jmp);
    converter->xmin=0;
    converter->ymin=0;
    converter->xmax=0;
    converter->ymax=0;
}

static void
_glitter_scan_converter_fini(glitter_scan_converter_t *self)
{
    if (self->spans != self->spans_embedded)
    free (self->spans);

    polygon_fini(self->polygon);
    cell_list_fini(self->coverages);

    self->xmin=0;
    self->ymin=0;
    self->xmax=0;
    self->ymax=0;
}

static grid_scaled_t
int_to_grid_scaled(int i, int scale)
{
    /* Clamp to max/min representable scaled number. */
    if (i >= 0) {
    if (i >= INT_MAX/scale)
        i = INT_MAX/scale;
    }
    else {
    if (i <= INT_MIN/scale)
        i = INT_MIN/scale;
    }
    return i*scale;
}

#define int_to_grid_scaled_x(x) int_to_grid_scaled((x), GRID_X)
#define int_to_grid_scaled_y(x) int_to_grid_scaled((x), GRID_Y)

I glitter_status_t
glitter_scan_converter_reset(
                 glitter_scan_converter_t *converter,
                 int xmin, int ymin,
                 int xmax, int ymax)
{
    glitter_status_t status;
    int max_num_spans;

    converter->xmin = 0; converter->xmax = 0;
    converter->ymin = 0; converter->ymax = 0;

    max_num_spans = xmax - xmin + 1;

    if (max_num_spans > ARRAY_LENGTH(converter->spans_embedded)) {
    converter->spans = _cairo_malloc_ab (max_num_spans,
                         sizeof (cairo_half_open_span_t));
    if (unlikely (converter->spans == NULL))
        return _cairo_error (CAIRO_STATUS_NO_MEMORY);
    } else
    converter->spans = converter->spans_embedded;

    xmin = int_to_grid_scaled_x(xmin);
    ymin = int_to_grid_scaled_y(ymin);
    xmax = int_to_grid_scaled_x(xmax);
    ymax = int_to_grid_scaled_y(ymax);

    active_list_reset(converter->active);
    cell_list_reset(converter->coverages);
    status = polygon_reset(converter->polygon, ymin, ymax);
    if (status)
    return status;

    converter->xmin = xmin;
    converter->xmax = xmax;
    converter->ymin = ymin;
    converter->ymax = ymax;
    return GLITTER_STATUS_SUCCESS;
}

/* INPUT_TO_GRID_X/Y (in_coord, out_grid_scaled, grid_scale)
 *   These macros convert an input coordinate in the client's
 *   device space to the rasterisation grid.
 */
/* Gah.. this bit of ugly defines INPUT_TO_GRID_X/Y so as to use
 * shifts if possible, and something saneish if not.
 */
#if !defined(INPUT_TO_GRID_Y) && defined(GRID_Y_BITS) && GRID_Y_BITS <= GLITTER_INPUT_BITS
#  define INPUT_TO_GRID_Y(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_Y_BITS)
#else
#  define INPUT_TO_GRID_Y(in, out) INPUT_TO_GRID_general(in, out, GRID_Y)
#endif

#if !defined(INPUT_TO_GRID_X) && defined(GRID_X_BITS) && GRID_X_BITS <= GLITTER_INPUT_BITS
#  define INPUT_TO_GRID_X(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_X_BITS)
#else
#  define INPUT_TO_GRID_X(in, out) INPUT_TO_GRID_general(in, out, GRID_X)
#endif

#define INPUT_TO_GRID_general(in, out, grid_scale) do {     \
    long long tmp__ = (long long)(grid_scale) * (in);   \
    tmp__ >>= GLITTER_INPUT_BITS;               \
    (out) = tmp__;                      \
} while (0)

/* Add a new polygon edge from pixel (x1,y1) to (x2,y2) to the scan
 * converter.  The coordinates represent pixel positions scaled by
 * 2**GLITTER_PIXEL_BITS.  If this function fails then the scan
 * converter should be reset or destroyed.  Dir must be +1 or -1,
 * with the latter reversing the orientation of the edge. */
I void
glitter_scan_converter_add_edge (glitter_scan_converter_t *converter,
                 const cairo_edge_t *edge)
{
    cairo_edge_t e;

    INPUT_TO_GRID_Y (edge->top, e.top);
    INPUT_TO_GRID_Y (edge->bottom, e.bottom);
    if (e.top >= e.bottom)
    return;

    /* XXX: possible overflows if GRID_X/Y > 2**GLITTER_INPUT_BITS */
    INPUT_TO_GRID_Y (edge->line.p1.y, e.line.p1.y);
    INPUT_TO_GRID_Y (edge->line.p2.y, e.line.p2.y);
    if (e.line.p1.y == e.line.p2.y)
    e.line.p2.y++; /* little fudge to prevent a div-by-zero */

    INPUT_TO_GRID_X (edge->line.p1.x, e.line.p1.x);
    INPUT_TO_GRID_X (edge->line.p2.x, e.line.p2.x);

    e.dir = edge->dir;

    polygon_add_edge (converter->polygon, &e);
}

static void
step_edges (struct active_list *active, int count)
{
    struct edge *edge;

    count *= GRID_Y;
    for (edge = active->head.next; edge != &active->tail; edge = edge->next) {
    edge->height_left -= count;
    if (! edge->height_left) {
        edge->prev->next = edge->next;
        edge->next->prev = edge->prev;
        active->min_height = -1;
    }
    }
}

static glitter_status_t
blit_a8 (struct cell_list *cells,
     cairo_span_renderer_t *renderer,
     cairo_half_open_span_t *spans,
     int y, int height,
     int xmin, int xmax)
{
    struct cell *cell = cells->head.next;
    int prev_x = xmin, last_x = -1;
    int16_t cover = 0, last_cover = 0;
    unsigned num_spans;

    if (cell == &cells->tail)
    return CAIRO_STATUS_SUCCESS;

    /* Skip cells to the left of the clip region. */
    while (cell->x < xmin) {
    cover += cell->covered_height;
    cell = cell->next;
    }
    cover *= GRID_X*2;

    /* Form the spans from the coverages and areas. */
    num_spans = 0;
    for (; cell->x < xmax; cell = cell->next) {
    int x = cell->x;
    int16_t area;

    if (x > prev_x && cover != last_cover) {
        spans[num_spans].x = prev_x;
        spans[num_spans].coverage = GRID_AREA_TO_ALPHA (cover);
        last_cover = cover;
        last_x = prev_x;
        ++num_spans;
    }

    cover += cell->covered_height*GRID_X*2;
    area = cover - cell->uncovered_area;

    if (area != last_cover) {
        spans[num_spans].x = x;
        spans[num_spans].coverage = GRID_AREA_TO_ALPHA (area);
        last_cover = area;
        last_x = x;
        ++num_spans;
    }

    prev_x = x+1;
    }

    if (prev_x <= xmax && cover != last_cover) {
    spans[num_spans].x = prev_x;
    spans[num_spans].coverage = GRID_AREA_TO_ALPHA (cover);
    last_cover = cover;
    last_x = prev_x;
    ++num_spans;
    }

    if (last_x < xmax && last_cover) {
    spans[num_spans].x = xmax;
    spans[num_spans].coverage = 0;
    ++num_spans;
    }

    /* Dump them into the renderer. */
    return renderer->render_rows (renderer, y, height, spans, num_spans);
}

#define GRID_AREA_TO_A1(A)  ((GRID_AREA_TO_ALPHA (A) > 127) ? 255 : 0)
static glitter_status_t
blit_a1 (struct cell_list *cells,
     cairo_span_renderer_t *renderer,
     cairo_half_open_span_t *spans,
     int y, int height,
     int xmin, int xmax)
{
    struct cell *cell = cells->head.next;
    int prev_x = xmin, last_x = -1;
    int16_t cover = 0;
    uint8_t coverage, last_cover = 0;
    unsigned num_spans;

    if (cell == &cells->tail)
    return CAIRO_STATUS_SUCCESS;

    /* Skip cells to the left of the clip region. */
    while (cell->x < xmin) {
    cover += cell->covered_height;
    cell = cell->next;
    }
    cover *= GRID_X*2;

    /* Form the spans from the coverages and areas. */
    num_spans = 0;
    for (; cell->x < xmax; cell = cell->next) {
    int x = cell->x;
    int16_t area;

    coverage = GRID_AREA_TO_A1 (cover);
    if (x > prev_x && coverage != last_cover) {
        last_x = spans[num_spans].x = prev_x;
        last_cover = spans[num_spans].coverage = coverage;
        ++num_spans;
    }

    cover += cell->covered_height*GRID_X*2;
    area = cover - cell->uncovered_area;

    coverage = GRID_AREA_TO_A1 (area);
    if (coverage != last_cover) {
        last_x = spans[num_spans].x = x;
        last_cover = spans[num_spans].coverage = coverage;
        ++num_spans;
    }

    prev_x = x+1;
    }

    coverage = GRID_AREA_TO_A1 (cover);
    if (prev_x <= xmax && coverage != last_cover) {
    last_x = spans[num_spans].x = prev_x;
    last_cover = spans[num_spans].coverage = coverage;
    ++num_spans;
    }

    if (last_x < xmax && last_cover) {
    spans[num_spans].x = xmax;
    spans[num_spans].coverage = 0;
    ++num_spans;
    }
    if (num_spans == 1)
    return CAIRO_STATUS_SUCCESS;

    /* Dump them into the renderer. */
    return renderer->render_rows (renderer, y, height, spans, num_spans);
}


I void
glitter_scan_converter_render(glitter_scan_converter_t *converter,
                  unsigned int winding_mask,
                  int antialias,
                  cairo_span_renderer_t *renderer)
{
    int i, j;
    int ymax_i = converter->ymax / GRID_Y;
    int ymin_i = converter->ymin / GRID_Y;
    int xmin_i, xmax_i;
    int h = ymax_i - ymin_i;
    struct polygon *polygon = converter->polygon;
    struct cell_list *coverages = converter->coverages;
    struct active_list *active = converter->active;
    struct edge *buckets[GRID_Y] = { 0 };

    xmin_i = converter->xmin / GRID_X;
    xmax_i = converter->xmax / GRID_X;
    if (xmin_i >= xmax_i)
    return;

    /* Render each pixel row. */
    for (i = 0; i < h; i = j) {
    int do_full_row = 0;

    j = i + 1;

    /* Determine if we can ignore this row or use the full pixel
     * stepper. */
    if (! polygon->y_buckets[i]) {
        if (active->head.next == &active->tail) {
        active->min_height = INT_MAX;
        active->is_vertical = 1;
        for (; j < h && ! polygon->y_buckets[j]; j++)
            ;
        continue;
        }

        do_full_row = can_do_full_row (active);
    }

    if (do_full_row) {
        /* Step by a full pixel row's worth. */
        full_row (active, coverages, winding_mask);

        if (active->is_vertical) {
        while (j < h &&
               polygon->y_buckets[j] == NULL &&
               active->min_height >= 2*GRID_Y)
        {
            active->min_height -= GRID_Y;
            j++;
        }
        if (j != i + 1)
            step_edges (active, j - (i + 1));
        }
    } else {
        int sub;

        polygon_fill_buckets (active,
                  polygon->y_buckets[i],
                  (i+ymin_i)*GRID_Y,
                  buckets);

        /* Subsample this row. */
        for (sub = 0; sub < GRID_Y; sub++) {
        if (buckets[sub]) {
            active_list_merge_edges_from_bucket (active, buckets[sub]);
            buckets[sub] = NULL;
        }

        sub_row (active, coverages, winding_mask);
        }
    }

    if (antialias)
        blit_a8 (coverages, renderer, converter->spans,
             i+ymin_i, j-i, xmin_i, xmax_i);
    else
        blit_a1 (coverages, renderer, converter->spans,
             i+ymin_i, j-i, xmin_i, xmax_i);
    cell_list_reset (coverages);

    active->min_height -= GRID_Y;
    }
}

struct _cairo_tor_scan_converter {
    cairo_scan_converter_t base;

    glitter_scan_converter_t converter[1];
    cairo_fill_rule_t fill_rule;
    cairo_antialias_t antialias;

    jmp_buf jmp;
};

typedef struct _cairo_tor_scan_converter cairo_tor_scan_converter_t;

static void
_cairo_tor_scan_converter_destroy (void *converter)
{
    cairo_tor_scan_converter_t *self = converter;
    if (self == NULL) {
    return;
    }
    _glitter_scan_converter_fini (self->converter);
    free(self);
}

cairo_status_t
_cairo_tor_scan_converter_add_polygon (void     *converter,
                       const cairo_polygon_t *polygon)
{
    cairo_tor_scan_converter_t *self = converter;
    int i;

#if 0
    FILE *file = fopen ("polygon.txt", "w");
    _cairo_debug_print_polygon (file, polygon);
    fclose (file);
#endif

    for (i = 0; i < polygon->num_edges; i++)
     glitter_scan_converter_add_edge (self->converter, &polygon->edges[i]);

    return CAIRO_STATUS_SUCCESS;
}

static cairo_status_t
_cairo_tor_scan_converter_generate (void            *converter,
                    cairo_span_renderer_t   *renderer)
{
    cairo_tor_scan_converter_t *self = converter;
    cairo_status_t status;

    if ((status = setjmp (self->jmp)))
    return _cairo_scan_converter_set_error (self, _cairo_error (status));

    glitter_scan_converter_render (self->converter,
                   self->fill_rule == CAIRO_FILL_RULE_WINDING ? ~0 : 1,
                   self->antialias != CAIRO_ANTIALIAS_NONE,
                   renderer);
    return CAIRO_STATUS_SUCCESS;
}

cairo_scan_converter_t *
_cairo_tor_scan_converter_create (int           xmin,
                  int           ymin,
                  int           xmax,
                  int           ymax,
                  cairo_fill_rule_t fill_rule,
                  cairo_antialias_t antialias)
{
    cairo_tor_scan_converter_t *self;
    cairo_status_t status;

    self = malloc (sizeof(struct _cairo_tor_scan_converter));
    if (unlikely (self == NULL)) {
    status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
    goto bail_nomem;
    }

    self->base.destroy = _cairo_tor_scan_converter_destroy;
    self->base.generate = _cairo_tor_scan_converter_generate;

    _glitter_scan_converter_init (self->converter, &self->jmp);
    status = glitter_scan_converter_reset (self->converter,
                       xmin, ymin, xmax, ymax);
    if (unlikely (status))
    goto bail;

    self->fill_rule = fill_rule;
    self->antialias = antialias;

    return &self->base;

 bail:
    self->base.destroy(&self->base);
 bail_nomem:
    return _cairo_scan_converter_create_in_error (status);
}
#endif